//
// Description: 6018. 根据描述创建二叉树
// Created by Loading on 2022/3/6.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

TreeNode *createBinaryTree(vector<vector<int>> &descriptions) {
    constexpr int N = 100010;
    vector<TreeNode *> nodes(N);
    vector<int> has_father(N);

    for (auto v : descriptions) {
        // 已创建则取出使用，否则创建新节点
        TreeNode *root = nodes[v[0]] ? nodes[v[0]] : nodes[v[0]] = new TreeNode(v[0]);
        TreeNode *node = nodes[v[1]] ? nodes[v[1]] : nodes[v[1]] = new TreeNode(v[1]);
        if (v[2] == 1) {
            root->left = node;
        } else {
            root->right = node;
        }
        has_father[v[1]] = 1;
    }
    // 寻找根节点
    for (int i = 0; i < N; ++i) {
        if (nodes[i] && has_father[i] == 0) {
            return nodes[i];
        }
    }

    return nullptr;
}

int main() {
    vector<vector<int>> descriptions{{1, 2, 1},
                                     {2, 3, 0},
                                     {3, 4, 1}};
    auto root = createBinaryTree(descriptions);
    string s = printfTreeNodeOfLevel(root);
    cout << s << endl;

    return 0;
}